package com.li.list;

public class 链表中环的入口结点 {
	public static void main(String[] args) {
		Node head = new Node();
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);

		head.next = node1;
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		node5.next = node6;
		node6.next = node3;
		
		System.out.println(entryNodeOfLoop(head).value);
	}

	public static Node entryNodeOfLoop(Node pHead){
		if(pHead==null|| pHead.next==null|| pHead.next.next==null)
			return null;
		Node fast=pHead.next.next;
		Node slow=pHead.next;
		/////先判断有没有环
		while(fast!=slow){
			if(fast.next!=null&& fast.next.next!=null){
				fast=fast.next.next;
				slow=slow.next;
			}else{
				//没有环,返回
				return null;
			}
		}
		//循环出来的话就是有环，且此时fast==slow.
		fast=pHead;
		while(fast!=slow){
			fast=fast.next;
			slow=slow.next;
		}
		return slow;

	}
}
